// https://leetcode.cn/problems/unique-paths/

// 题干：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
//      机器人每次只能向下或者向右移动一步。
//      机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
//      问总共有多少条不同的路径？

// 示例：输入：m = 3, n = 7
//       输出：28

// 碎语：画出图像，让dfs表示到达i，j位置的时候所需要的步数
//       发现只需要关注上面和左边的dfs，注意i或j等于0的特殊情况
//       和两个都在起始点的情况

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int uniquePaths(int m, int n)
    {
        vector<vector<int>> memo(m + 1, vector<int>(n + 1)); // 这次把备忘录放局部
        return dfs(m, n, memo);
    }

    int dfs(int i, int j, vector<vector<int>>& memo)
    {
        // 调用时候查询
        if (memo[i][j]) return memo[i][j];

        if (i == 0 || j == 0) return 0;
        if (i == 1 && j == 1)
        {
            memo[i][j] = 1;
            return 1;
        }

        memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);
        return memo[i][j];
    }
};

int main()
{
    Solution sol;

    cout << sol.uniquePaths(3, 7) << endl;
    
    return 0;
}